1. Field of the Invention
The invention relates to communication of data between at least one transmitter and at least one receiver. It is particularly applicable to communication systems where the data is transmitted over a time-variant and/or frequency-variant channel, such as in mobile communication systems or satellite communication.
2. Description of the Related Art
The following sections will concentrate on the downlink transmission, however without loss of generality the same is valid for uplink transmission.
Dynamic Channel Allocation (DCA)
In wireless communication systems employing Dynamic Channel Allocation (DCA) schemes, at least part of the air interface resources are assigned dynamically to different users (mobile stations, MS). See R, van Nee, R. Prasad, “OFDM for Wireless Multimedia Communications”, Artech House, ISBN 0 89006 530 6, 2000, pp. 213-228 and H. Rohling and R. Grunheid, “Performance of an OFDM-TDMA mobile communication system,” in Proc. IEEE Vehicular Technology Conf. (VTC'96), Atlanta, Ga., pp. 1589-1593, 1996. Those dynamically allocated resources are usually defined by Shared Physical Channels, where a Shared Physical Channel corresponds to e.g. one or multiple bundled codes in a Code Division Multiple Access (CDMA) system, one or multiple bundled subcarriers (subchannels) in an Orthogonal Frequency Division Multiplex Access (OFDMA) system or to combinations of those in an Orthogonal Frequency Code Division Multiplex Access (OFCDMA) or an Multi Carrier Code Division Multiple Access (MC CDMA) system.
For the context of this description, a subchannel shall be regarded as comprising at least one subcarrier, wherein the subcarriers belonging to a subchannel may be selected adjacent to each other or distributed over the transmission bandwidth. The number of subcarriers per subchannel may vary between subchannels and/or be configured dynamically.
FIG. 1 and FIG. 2 show DCA schemes for systems with a single and multiple Shared Physical Channels respectively, where a PHY Frame reflects the unit for which a so called scheduler (PHY/MAC Scheduler) performs the DCA.
It should be noted, that a Multiple Shared Channel system may also be viewed as a Single Shared Channel System, where the Single Shared Channel consists out of multiple subchannels (resources). In this case multiple users (mobile stations) may be allocated on the same Shared Channel at a time, but on different subchannels.
FIG. 1 illustrates a structure where data for four mobile stations U1 . . . U4 is transmitted over one shared physical channel 102. The time axis is represented by arrow 101. Boxes 103 to 108 represent PHY frames, wherein, as an illustrative example, frame 106 carries data for a first mobile station, frame 103 carries data for a second mobile station, frames 104 and 108 carry data for a third mobile station and frames 105 and 107 carry data for a fourth mobile station. In this example, a frequency or code division duplex system is shown, where one resource/subchannel (i.e. frequency band or code) is continuously available for the depicted shared physical channel. In case of TDD, where an uplink PHY channel and a downlink PHY channel share one frequency or code, there would be gaps between the frames or within the frames of one channel corresponding to the duration of the transmission of a channel in the opposite direction. For this case, all description below would likewise be applicable as well.
FIG. 2 illustrates the case where N shared physical channels 202 to 205 transmit data designated to four mobile stations. Arrow 201 represents the time axis. Columns 230 to 235 represent the time units of PHY frames for all channels. Boxes 206 to 229 represent data units defined by PHY channels and PHY frames. For example, data in boxes 206 to 211 is transmitted over PHY channel 1 and data in boxes 206, 212, 218 and 224 is transmitted during frame 230. In the given example, the data units 208, 212, 220, 221, 223, 225 and 227 carry data for a first mobile station U1, 206, 207, 215, 217, 226 and 228 carry data for a second mobile station U2, 209, 210, 224 and 229 carry data for a third mobile station U3 and 211, 213, 214, 216, 218, 219 and 222 carry data for a fourth mobile station U4.
For the 3rd Generation CDMA mobile communication systems, DCA on a packet basis has been introduced by HSDPA (High Speed Downlink Packet Access) for the 3GPP (UMTS) standard (3GPP, Technical Specification 25.308; High Speed Downlink Packet Access (HSDPA); Overall description; Stage 2, v. 5.3.0, December 2002), and by HDR (High Data Rate) for the 3GPP2 CDMA 2000 standard (QUALCOMM, “1xEV: 1x Evolution IS-856 TIA/EIA Standard—Airlink Overview,” available at http://www.qualcomm.com).
Link Adaptation (LA) Techniques
In order to utilize the benefits from DCA, it is usually combined with Link Adaptation (LA) techniques such as Adaptive Modulation and Coding (AMC) and Hybrid Automatic Repeat reQuest (HARQ).
Adaptive Modulation and Coding (AMC)
Employing Adaptive Modulation and Coding (AMC), the data rate within a PHY Frame for a scheduled user will be adapted dynamically to the instantaneous channel quality of the respective link by changing the Modulation and Coding Scheme (MCS). Naturally, this requires a channel quality estimate at the transmitter for the link to the respective receiver. For details of AMC, refer to H. Rohling and R. Grunheid, cited above, 3GPP TS25.308 cited above, A. Burr, Modulation and Coding for Wireless Communications, Pearson Education, Prentice Hall, ISBN 0 201 39857 5, 2001, pp. 255-267, and C. Y. Wong, R. S. Cheng, K. B. Letaief, and R. D. Murch “Multiuser OFDM with Adaptive Subcarrier, Bit, and Power Allocation,” IEEE J. Select. Areas Commun., vol. 17, no. 10, October 1999.
Hybrid Automatic Repeat reQuest (HARQ)
To cope with the PHY Frame error rates caused by the selection of the MCS level (e.g. by incorrect channel quality estimation or inherent to the selected MCS level for a given channel quality), Hybrid Automatic Repeat reQuest (HARQ) schemes are used to control the data/packet loss rate (residual PHY Frame error rate after retransmissions) delivered to the next layer (or to the service/application). See H. Rohling and R. Grunheid, cited above, S. Kallel, “Analysis of a type II hybrid ARQ scheme with code combining,” IEEE Transactions on Communications, Vol. 38, No. 8, August 1990, S. Lin, D. J. Costello Jr., “Error Control Coding: Fundamentals and Applications”, Prentice-Hall, 1983, pp. 458-497, and S. Lin, D. J. Costello, M. J. Miller, “Automatic repeat request error control schemes,” IEEE Commun. Mag., vol. 22, no. 12, pp. 5-17, December 1984.
Scheduler
In a system making use of DCA and LA (AMC and/or HARQ), a MAC/PHY Scheduler entity decides which recourses are assigned to which mobile station. A commonly used approach is to use centralized scheduling, where the scheduler is located in the transmitter (base station in the downlink case).
Common objectives of the scheduler are to achieve fairness between users, maximize system throughput and/or fulfill Quality of Service (QoS) requirements (e.g. delay, data rate, loss rate, jitter) for the applications/flows served to the scheduled mobile stations.
Proportional Fair (PF) Scheduler
The Proportional Fair scheduler (see e.g. J. M. Holzman, “Asymptotic analysis of proportional fair algorithm,” Proc. IEEE PIMRC 2001, San Diego, Calif., pp. F 33-F 37, October 2001) maintains an average data rate transmitted to each user within a defined time window and examines the ratio of the instantaneous to the average channel conditions (or ratio of the instantaneous possible data rate to the average data rate) experienced by different users and chooses the user with the maximum ratio. This scheduler increases the system throughput with respect to Round Robin scheduling, while maintaining long-term fairness with respect to the allocated resources. The conventional Proportional Fair (PF) scheduler implementation works as follows:                For a given Shared Physical Channel at each scheduling time tn (e.g. PHY Frame according to FIG. 1), the priority function Pm(tn) is computed for each mobile station m:        
                                                        P              m                        ⁡                          (                              t                n                            )                                =                                                    DRC                m                            ⁡                              (                                  t                  n                                )                                                                    R                m                            ⁡                              (                                  t                  n                                )                                                    ,                            (        1        )            where tn denotes the time index (n-th PHY Frame/time slot), DRCm(tn) denotes the data rate potentially achievable for mobile station m at time tn according to the AMC (generally computed using either the SIR feedback from the MS or the known/estimated SIR value for the link at the BS) and Rm(tn) denotes the average rate served to this mobile station up to time tn (usually time windowed).                The mobile station m* with the highest priority Pm(tn) is scheduled at the current frame:        
                                                                        m                *                            =                            ⁢                                                                    arg                    ⁢                                                                                  ⁢                    max                                    m                                ⁢                                  {                                                            P                      m                                        ⁡                                          (                                              t                        n                                            )                                                        }                                                                                                        =                            ⁢                                                                    arg                    ⁢                                                                                  ⁢                    max                                    m                                ⁢                                                      {                                                                                            DRC                          m                                                ⁡                                                  (                                                      t                            n                                                    )                                                                                                                      R                          m                                                ⁡                                                  (                                                      t                            n                                                    )                                                                                      }                                    .                                                                                        (        2        )            
The PF scheduler is also called riding-on-peak scheduler, since a MS is preferably scheduled if its instantaneous channel condition has a peak. A general assumption is that all MS within a system have similar channel statistics. The PF scheduler maintains fairness on long-term basis; however, on a short-term basis it may be unfair.
The PF scheduler can be generalized by introducing coefficients α and β. This way the trade-off between fairness and system throughput performance can be tweaked. Hence, the selection of a mobile station m* to be scheduled works as follows:
                                          m            *                    =                                                    arg                ⁢                                                                  ⁢                max                            m                        ⁢                          {                                                                    [                                                                  DRC                        m                                            ⁡                                              (                                                  t                          n                                                )                                                              ]                                    α                                                                      [                                                                  R                        m                                            ⁡                                              (                                                  t                          n                                                )                                                              ]                                    β                                            }                                      ,                            (        3        )            where α and β are typically non-negative.
The following combinations of α and β denote special cases:                α=1 β=1: Conventional PF scheduler (see equations (1) and (2)).        α=1 β=0: Max Rate (MR) scheduler: the mobile station, which can achieve the highest rate is scheduled.        α=0 β=1: Fair Scheduler with respect to data rate delivered to the mobile stations (not fair with respect to air-interface resources).        
The (generalized) PF scheduler does not consider QoS requirements.
In the next section a scheduling approach is described which considers PHY channel states as well as QoS issues.
M-LWDF and “Exponential Rule” Scheduler
The M-LWDF (Modified-Largest Weighted Delay First) (see M. Andrews, et al., “Providing quality of service over a shared wireless link,” IEEE Commun. Mag., pp. 150-154, February 2001) and “Exponential Rule” (see Sanjay Shakkottai, Alexander L. Stolyar, “Scheduling Algorithms for a Mixture of Real-Time and Non-Real Time Data in HDR,” Technical Report, University of Illinois at Urbana-Champaign, Bell Laboratories, Lucent Technologies) are scheduling approaches for efficient QoS support and at the same time efficient air interface utilization for HDR, where it is assumed that only a single user receives data at a time, i.e. a single Shared Physical Channel 102 is assumed.
A block diagram of the M-LWDF and “Exponential Rule” scheduler is shown in FIG. 3. Unit 301 in physical layer/medium access control (MAC) layer scheduler 300 selects packets of queues 302 . . . 304, corresponding to users m=1 . . . M, for transmission over shared physical channel 102 employing adaptive modulation and coding in AMC unit 305. Unit 306 calculates a term Wm(tn) or an exponential rule term depending on Wm(tn). These terms reflect the state of the queues. Unit 307 calculates a potential data rate DRCm(tn) and an average data rate Rm(tn) for user m. These values reflect the actual channel states SIRm(tn) for the M users. Unit 301 calculates a priority function for each user m and each frame tn, based on both Wm(tn) or the exponential rule term and Rm(tn), and schedules the HOL packet (Head-Of-Line; next packet in queue, which generally is the packet with the largest delay) of the queue with the highest priority function value as next packet to be transmitted.
For M users (mobile stations) in systems employing M-LWDF, at each scheduling instant tn the user m* is selected for transmission for whom the following priority function is maximal:
                                          P            m                    ⁡                      (                          t              n                        )                          =                                            γ              m                        ⁡                          (                              t                n                            )                                ⁢                                    W              m                        ⁡                          (                              t                n                            )                                ⁢                                    DRC              m                        ⁡                          (                              t                n                            )                                                          (        4        )                                                      m            *                    =                                                    arg                ⁢                                                                  ⁢                max                            m                        ⁢                          {                                                P                  m                                ⁡                                  (                                      t                    n                                    )                                            }                                      ,                            (        5        )            where DRCm(tn) denotes the available data rate for user m at time tn (same as in equations (1) to (3) for the PF scheduler) and Wm(tn) denotes the delay of the HOL packet of the flow serving user m. For some flows, the HOL packet delay Wm(tn) may be replaced by a parameter Qm(tn) which stands for the packet queue length in the transmit buffer (see M. Andrews, et al., cited above).
As can be seen from equation (4) the priority function depends on the current channel state of the user (reflected by the potential data rate DRCm(tn)), on the current delay/buffer status of the packet queue and on value γm. This way the M-LWDF scheduler considers PHY issues as well as QoS requirements.
According to M. Andrews, et al., cited above, a preferred implementation solution for the M-LWDF yields γm=am/Rm(tn) and am=−log(δm)/Tm with Rm(tn) being the average data rate for user m. Tm and δm represent the delay threshold and the maximum probability of exceeding it for user m (static QoS requirements), i.e. they denote the QoS requirement Pr {Wm>Tm}≦δm, where Wm denotes the packet delay. Equation (4) then yields:
                                                        P              m                        ⁡                          (                              t                n                            )                                =                                                                                          -                                          log                      ⁡                                              (                                                  δ                          m                                                )                                                                                                  T                    m                                                  ⁢                                                      W                    m                                    ⁡                                      (                                          t                      n                                        )                                                                              ︸                                  QoS                  ⁢                                                                          ⁢                  related                  ⁢                                                                          ⁢                  term                                                      ⁢                                                                                DRC                    m                                    ⁡                                      (                                          t                      n                                        )                                                                                        R                    m                                    ⁡                                      (                                          t                      n                                        )                                                                              ︸                                                      PHY                    ⁢                                                                                  ⁢                    related                    ⁢                                                                                  ⁢                    term                                                        (                                          PF                      ⁢                                                                                          ⁢                      scheduler                                        )                                                                                      ,                            (        6        )            
More details on the M-LWDF scheduler such as e.g. a possible combination with a Token Bucket algorithm are given in M. Andrews, et al., cited above. The M-LWDF scheduler is furthermore described in published European Patent Application no. EP1130872A1.
For the “Exponential Rule” scheduler simply equation (4) is modified such that the HOL packet delay Wm(tn) is replaced by an exponential term (see Shakkottai and Stolyar, cited above). The priority function then yields
                                                        P              m                        ⁡                          (                              t                n                            )                                =                                    γ              m                        ⁢                          exp              ⁡                              (                                                                                                    p                        m                                            ⁢                                                                        W                          m                                                ⁡                                                  (                                                      t                            n                                                    )                                                                                      -                                                                  p                        ⁢                                                                                                  ⁢                                                  W                          tot                                                                    _                                                                            1                    +                                                                                            p                          ⁢                                                                                                          ⁢                                                      W                            tot                                                                          _                                                                                            )                                      ⁢                                          DRC                m                            ⁡                              (                                  t                  n                                )                                                    ⁢                                  ⁢        with                            (        7        )                                                                    p              ⁢                                                          ⁢                              W                tot                                      _                    =                                    1              M                        ⁢                                          ∑                m                            ⁢                                                p                  m                                ⁢                                                      W                    m                                    ⁡                                      (                                          t                      n                                        )                                                                                      ,                            (        8        )            where γm and pm are sets of positive constants.
A further modified version of the “Exponential Rule” scheduler is described in Kapseok Chang and Youngnam Han, “QoS-based adaptive scheduling for a mixed service in HDR system”, PIMRC 2002, vol. 4, pp. 1914-1918, September 2002.
It should be noted, that in the aforementioned M-LWDF based schedulers, the PHY dependent terms (DRCm(tn) and Rm(tn)) and the QoS term (Wm(tn) in case of M-LWDF) do not depend on each other and can be calculated independently.
As traffic on communication systems is increasing and Quality of Service demands are rising, there is a strong need for an improved scheduling algorithm which provides enhanced air interface efficiency and meets QoS demands in a better way. Moreover there is a need for a scheduling algorithm which supports multiple Shared Channel configurations.